import java.util.ArrayList;
import java.util.Iterator;

public class Arrays {
    public static int removeDuplicates(int[] nums) {
        if (nums.length == 0)
            return 0;
        //判断无输入
        int number = 0;//标记计数
        for (int i=0; i < nums.length ; i++) {
            if ( nums[i] != nums[number] ) {
                number++;
                nums[number] = nums[i];
            }
        }
        number+=1; //标记+1即为数字个数
        return number;
    }

    public int maxProfit(int[] prices) {
        int profit=0;
        int len=prices.length;
        if(len<2)
            return 0;
        int pro[]=new int[len-1];
        for(int i=0;i<len-1;i++){
            pro[i]=prices[i+1]-prices[i];
        }
        for (int i=0;i<len-1;i++){
            if(pro[i]>0)profit+=pro[i];
        }
        return profit;
    }

    public static void rotate(int[] nums, int k) {
        int len = nums.length;
        int temp;

        //安全性检查
        if(nums==null||k<0)
            return;
        for (int i = 0; i < k; i++) {
            temp = nums[len-1];
            for (int j = len-1 ; j >0; j--) {
                nums[j] = nums[j-1];
            }
            nums[0] = temp;
        }
    }

    public boolean containsDuplicate(int[] nums) {
        for(int i=0;i<nums.length-1;i++){
            for(int j=i+1;j<nums.length;j++){
                if(nums[i]==nums[j])return true;
            }
        }
        return false;
    }

    public int singleNumber(int[] nums) {


        int num = 0;
        for(int i = 0; i < nums.length; i++) {
            num ^= nums[i];
        }
        return num;
    }

    public static int[] plusOne(int[] digits) {
        int len=digits.length;
        digits[len-1]+=1;
        int c=0;
        while (digits[len-1]==10){
            digits[len-1]=0;
            len--;
            if(len==0){
                c=1;
                break;
            }
            digits[len-1]+=1;
        }
        int result[];
        if(c==1){
            result=new int[digits.length+1];
            result[0]=1;
            for (int i=0;i<len;i++){
                result[i+1]=digits[i];
            }
            return result;
        }else {
            return digits;
        }
    }
    public static void moveZeroes(int[] nums) {
        int zero=0;
        for(int i=0;i<nums.length;i++){
            if (nums[i]==0){
                continue;
            }
            if(zero==i){
                zero++;
                continue;
            }
            nums[zero]=nums[i];
            nums[i]=0;
            zero++;
        }
    }

    public static void rotate(int[][] matrix) {
        int len=matrix.length;
        for (int i=0;i<len/2;i++){
            int num=len-2*i;
            for (int j=i;j<i+num-1;j++){
                int offset=j-i;
                int temp=matrix[i][j];
                matrix[i][j]=matrix[i+num-1-offset][i];
                matrix[i+num-1-offset][i]=matrix[i+num-1][i+num-1-offset];
                matrix[i+num-1][i+num-1-offset]=matrix[i + offset][i + num - 1];
                matrix[i + offset][i + num - 1]=temp;
            }
        }
    }

    public int[] intersect(int[] nums1, int[] nums2) {
        ArrayList<Integer> list1=new ArrayList<>();
        ArrayList<Integer> list2=new ArrayList<>();
        for (int i=0;i<nums1.length;i++)
            list1.add(nums1[i]);
        for(int i=0;i<nums2.length;i++)
            list2.add(nums2[i]);

        if(nums1.length>nums2.length){

        }else {
            ArrayList<Integer> temp=list1;
            list1=list2;
            list2=temp;
        }

        int i=0,j=0;boolean flag=false;
        int len1=list1.size();
        int len2=list2.size();
        ArrayList<Integer> list3=new ArrayList<>();
        for(i=0;i<len1;i++){
            flag = false;
            int temp1=list1.get(i);
            for(j=0;j<len2;j++){
                int temp2=list2.get(j);
                if(temp1==temp2){list2.remove(j);flag=true;len2--;list3.add(temp1);break;}
            }
            if(flag){
                list1.remove(i);
                len1--;
                i--;
            }
        }
        int result[]=new int[list3.size()];

        Iterator<Integer> integerIterator1=list3.iterator();
        i=0;
        while (integerIterator1.hasNext()){
            result[i]=integerIterator1.next();
            i++;
        }
        return result;
    }

    public boolean isValidSudoku(char[][] board) {
        int row[][]=new int[9][9],column[][]=new int[9][9],square[][]=new int[9][9];
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                if(board[i][j]!='.')
                {
                    int k = i/3*3+j/3;
                    int number = board[i][j]-'0'-1;
                    if(row[i][number]==1||column[j][number]==1||square[k][number]==1)
                    {
                        return false;
                    }
                    row[i][number]=column[j][number]=square[k][number]=1;

                }
            }
        }
        return true;
    }
}
